package org.example.myleet.dfs;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;
import org.example.myleet.Utils.TreeNode;

import java.util.*;

public class DfsSolution {

    /**
     * 90【递归】子集 II
     * 7 ms
     * 幂集，所有元素的组合，组合内按升序排列，组合不重复
     * 使用深度优先搜索+回溯算法查找所有组合
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        List<Integer> combination = new ArrayList<>();
        Map<Integer, List<List<Integer>>> sumResultMap = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            dfs90(nums, i, result, combination, sumResultMap);
        }
        return result;
    }
    private void dfs90(int[] nums, int i, List<List<Integer>> result, List<Integer> combination, Map<Integer, List<List<Integer>>> sumResultMap) {
        if (i >= nums.length) {
            //递归搜索结束条件
            return;
        }
        for (int j = i; j < nums.length; ++j) {
            int n = nums[j];
            //加入组合中
            combination.add(n);
            //升序
            combination.sort(Comparator.comparingInt(o -> o));
            //使用求和缩小相同结果搜索范围
            int sum1 = 0;
            for (int j1 = 0; j1 < combination.size(); ++j1) {
                sum1 += combination.get(j1);
            }
            int sum = sum1;
            List<Integer> newCombination = null;
            if (sumResultMap.containsKey(sum)) {
                //找到key，则遍历缓存的结果以考察是否已经加入过结果中
                List<List<Integer>> combinations = sumResultMap.getOrDefault(sum, new ArrayList<>());
                List<Integer> sameCombination = null;
                for (List<Integer> c : combinations) {
                    //是否相同组合
                    boolean same = true;
                    if (c.size() != combination.size()) {
                        same = false;
                    } else {
                        for (int i1 = 0; i1 < c.size(); ++i1) {
                            if (!c.get(i1).equals(combination.get(i1))) {
                                same = false;
                                break;
                            }
                        }
                    }
                    if (same) {
                        sameCombination = c;
                        break;
                    }
                }
                if (null == sameCombination) {
                    //如果没有找到相同组合，则深拷贝此组合标，用于添加到结果中
                    newCombination = new ArrayList<>(combination);
                    combinations.add(newCombination);
                    sumResultMap.put(sum, combinations);
                }
            } else {
                //没找到key，直接添加到结果中
                newCombination = new ArrayList<>(combination);
                List<List<Integer>> combinations = new ArrayList<>();
                combinations.add(newCombination);
                sumResultMap.put(sum, combinations);
            }
            if (null != newCombination) {
                result.add(newCombination);
            }
            //继续下一位置搜索
            dfs90(nums, j + 1, result, combination, sumResultMap);
            //本子树深度搜索结束，回溯算法，将添加的n去掉
            for (int i1 = 0; i1 < combination.size(); ++i1) {
                if (combination.get(i1) == n) {
                    combination.remove(i1);
                    break;
                }
            }
        }
    }


    /**
     * 131【动态规划+DFS】分割回文串，9 ms
     */
    private Map<String, List<List<String>>> partitionMemo131;
    private Set<String> palindromeMemo131;
    private boolean isPalindrome131(String s) {
        //判断s是否回文，如果是则记忆化
        if (s.length() == 1 || palindromeMemo131.contains(s)) return true;
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            ++l;
            --r;
        }
        palindromeMemo131.add(s);
        return true;
    }
    private List<List<String>> dfs131(String s) {
        //分割s为回文串，如果已经分割过则直接取结果，否则就进行分割操作
        List<List<String>> result = partitionMemo131.get(s);
        if (null != result) return result;
        result = new ArrayList<>();
        if (isPalindrome131(s)) {
            //如果s自身是个回文串，则不分割的子串也是一种分割方式
            List<String> partition = new ArrayList<>(1);
            partition.add(s);
            result.add(partition);
        }
        //下面从左到右逐渐延长左边分割出的回文子串，右边的剩余子串作为一个未知的子问题通过DFS递归计算
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length() - 1; ++i) {
            sb.append(s.charAt(i));
            if (isPalindrome131(sb.toString())) {
                //如果sb是一个回文，则右边的剩余子串作为一个未知的子问题通过DFS递归计算
                List<List<String>> partitions = dfs131(s.substring(i + 1));
                if (!partitions.isEmpty()) {
                    //如果右边的剩余子串可以分割出结果，则每个结果进行复制，并加上sb，即可得到s的其中一个完整的分割方式，添加到结果result中
                    for (List<String> partition : partitions) {
                        List<String> p = new ArrayList<>(partition.size() + 1);
                        p.add(sb.toString());
                        p.addAll(partition);
                        result.add(p);
                    }
                }
            }
        }
        //记忆化s的分割结果
        partitionMemo131.put(s, result);
        return result;
    }
    public List<List<String>> partition(String s) {
        partitionMemo131 = new HashMap<>();
        palindromeMemo131 = new HashSet<>();
        return dfs131(s);
    }

    /**
     * 140【DFS】单词拆分 II
     */
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dictionary = new HashSet<>(wordDict);
        List<List<Integer>> possibleSolutions = new ArrayList<>();
        //检查是否有效，具体检查的是整个字符串s和wordDict中所有单词使用的字母是否都存在
        boolean valid = true;
        Set<Character> whatWeWant = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            whatWeWant.add(s.charAt(i));
        }
        Set<Character> whatWeHave = new HashSet<>();
        for (String word : dictionary) {
            for (int i = 0; i <word.length(); i++) {
                whatWeHave.add(word.charAt(i));
            }
        }
        for (Character c : whatWeWant) {
            if (!whatWeHave.contains(c)) {
                valid = false;
                break;
            }
        }
        if (valid) {
            findSpacing(s, dictionary, possibleSolutions, new ArrayList<>());
        }
        List<String> answer = new ArrayList<>();
        for (List<Integer> solution : possibleSolutions) {
            //根据每一个可能的答案拼出结果
            StringBuilder sb = new StringBuilder();
            for (int i=1; i<solution.size(); i++) {
                sb.append(s, solution.get(i-1), solution.get(i));
                sb.append(" ");
            }
            //去掉最后的空格
            sb.deleteCharAt(sb.length() - 1);
            answer.add(sb.toString());
        }
        return answer;
    }
    private void findSpacing(String s, Set<String> dictionary, List<List<Integer>> possibleSolution, List<Integer> spacingSolution) {
        //上一个开始计数的位置，空列表时第一位放0，表示从0开始计算
        int lastSpacePos = spacingSolution.size() > 0 ? spacingSolution.get(spacingSolution.size() - 1) : 0;
        if (0 == lastSpacePos) {
            spacingSolution.add(0);
        }
        //从下一位开始逐渐延伸当前观察的单词
        int nextSpacePos = lastSpacePos + 1;
        do {
            //截出这个单词，看看字典里面有没有
            String sub = s.substring(lastSpacePos, nextSpacePos);
            if (dictionary.contains(sub)) {
                //字典有的话，说明这可能是其中的一条路径，克隆一份路径，把这个位置加上去，放到下一次递归中
                List<Integer> clonedSolution = new ArrayList<>(spacingSolution);
                clonedSolution.add(nextSpacePos);
                if (nextSpacePos == s.length()) {
                    //如果下一个点到达字符串尾部，说明找到一个解
                    possibleSolution.add(clonedSolution);
                    return;
                }
                findSpacing(s, dictionary, possibleSolution, clonedSolution);
            }
            //继续向后延长单词，找出更多的可能性
            ++nextSpacePos;
        } while (nextSpacePos <= s.length());
        //找不到就算结束了这个路径的查找
    }

    /**
     * 222【二分法+DFS】完全二叉树的节点个数
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = findDepth222(root.left);
        int rightDepth = findDepth222(root.right);
        if (leftDepth == rightDepth) {
            //如果深度相同，说明左子节点是完全二叉树，节点数2^depth - 1，加上本次递归的根节点数量，恰好为2^depth，即1<<depth
            //接下来递归右子树，在里面用同样方法统计节点数
            return (1 << leftDepth) + countNodes(root.right);
        }
        //如果深度不相同，说明右子节点是完全二叉树，节点数2^depth - 1，加上本次递归的根节点数量，恰好为2^depth，即1<<depth
        //接下来递归左子树，在里面用同样方法统计节点数
        return (1 << rightDepth) + countNodes(root.left);
    }
    /**
     * 找节点深度，一直遍历左子节点直到底，遍历左子节点原因是此题优先填满底是左子节点
     */
    private int findDepth222(TreeNode n) {
        int depth = 0;
        if (n == null) {
            return depth;
        }
        TreeNode t = n;
        while (t != null) {
            ++depth;
            t = t.left;
        }
        return depth;
    }

    /**
     * 241【DFS+记忆化搜索】为运算表达式设计优先级
     */
    public List<Integer> diffWaysToCompute(String expression) {
        Set<Character> OPT_CHAR_SET = new HashSet<>(3);
        OPT_CHAR_SET.add('+');
        OPT_CHAR_SET.add('-');
        OPT_CHAR_SET.add('*');
        Map<String, List<Integer>> memo = new HashMap<>();
        return dfs241(expression, OPT_CHAR_SET, memo);
    }
    private List<Integer> dfs241(String expression, Set<Character> OPT_CHAR_SET, Map<String, List<Integer>> memo) {
        List<Integer> ways = memo.get(expression);
        if (null != ways) {
            //发现expression已经被计算过有多少钟可能，直接返回结果
            return memo.get(expression);
        }
        ways = new ArrayList<>();
        //寻找expression中操作符的位置
        List<Integer> optIndexes = new ArrayList<>();
        for (int i = 0; i < expression.length(); ++i) {
            if (OPT_CHAR_SET.contains(expression.charAt(i))) {
                optIndexes.add(i);
            }
        }
        if (optIndexes.size() == 0) {
            //expression就一个数字，直接返回就得了
            ways.add(Integer.parseInt(expression));
            return ways;
        }
        int r;
        for (int optIdx : optIndexes) {
            //将expression按操作符拆分成左右两边然后分别计算有多少种计算方案，然后两侧的计算方案的合并方式适用于乘法法则
            List<Integer> ways1 = dfs241(expression.substring(0, optIdx), OPT_CHAR_SET, memo);
            List<Integer> ways2 = dfs241(expression.substring(optIdx + 1), OPT_CHAR_SET, memo);
            char opt = expression.charAt(optIdx);
            for (Integer num1 : ways1) {
                for (Integer num2 : ways2) {
                    if (opt == '+') {
                        r = num1 + num2;
                    } else if (opt == '-') {
                        r = num1 - num2;
                    } else {
                        r = num1 * num2;
                    }
                    ways.add(r);
                }
            }
        }
        //记忆化expression的计算结果
        memo.put(expression, ways);
        return ways;
    }

    //p617. 合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (null == root1) return root2;
        if (null == root2) return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

    /**
     * 669【DFS】修剪二叉搜索树
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (null == root) {
            return null;
        }
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        TreeNode left = trimBST(root.left, low, high);
        TreeNode right = trimBST(root.right, low, high);
        root.left = left;
        root.right = right;
        return root;
    }

    /**
     * 671【DFS遍历二叉树】二叉树中第二小的节点
     */
    public int findSecondMinimumValue(TreeNode root) {
        if (root.left == null && root.right == null) {
            return -1;
        }
        Map<String, Long> resultMap = new HashMap<>();
        resultMap.put("bigger", Long.MAX_VALUE);
        dfs671(root, root.val, resultMap);
        if (resultMap.get("bigger") == Long.MAX_VALUE) return -1;
        return resultMap.get("bigger").intValue();
    }
    /**
     * 按题目叙述的规则，只要在遍历树的过程中找到仅仅大于smallest的值就是题目要返回的值，注意题目数据会给到Integer.MAX_VALUE的情况
     */
    private void dfs671(TreeNode n, int smallest, Map<String, Long> resultMap) {
        if (null == n) return;
        if (n.val > smallest) {
            long bigger = resultMap.get("bigger");
            resultMap.put("bigger", Math.min(bigger, n.val));
        }
        dfs671(n.left, smallest, resultMap);
        dfs671(n.right, smallest, resultMap);
    }

    /**
     * 935【动态规划】骑士拨号器
     */
    public int knightDialer(int n) {
        int MOD = 1000000007;
        int[][] next = new int[][]{
                {4, 6}, //0
                {6, 8}, //1
                {7, 9}, //2
                {4, 8}, //3
                {0, 3, 9}, //4
                {}, //5
                {0, 1, 7}, //6
                {2, 6}, //7
                {1, 3}, //8
                {2, 4} //9
        };
        long answer = 0;
        for (int x = 0; x <= 9; ++x) {
            long[] prevCnt = new long[10];
            prevCnt[x] = 1L;
            for (int i = 1; i < n; ++i) {
                long[] currCnt = new long[10];
                for (int j = 0; j < 10; ++j) {
                    int[] nextSteps = next[j];
                    for (int num : nextSteps) {
                        currCnt[num] += prevCnt[j];
                    }
                    currCnt[j] %= MOD;
                }
                prevCnt = currCnt;
            }
            for (int j = 0; j < 10; ++j) {
                answer += prevCnt[j];
                answer %= MOD;
            }
        }
        return (int) answer;
    }

    /**
     * 998【DFS】最大二叉树 II
     */
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (null == root) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            //如果val更大，则val作为新的根节点，又由于val在原始数组的最右侧，因此旧root节点是newRoot的左子节点
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        } else {
            //由于val在原始数组的最右侧，因此val一定是在右子节点部分插入
            root.right = insertIntoMaxTree(root.right, val);
            return root;
        }
    }

    //p1026
    private int max1026 = Integer.MIN_VALUE;
    public int maxAncestorDiff(TreeNode root) {
        dfs1026(root);
        return max1026;
    }
    private int[] dfs1026(TreeNode node) {
        int[] minMaxL = new int[]{node.val, node.val};
        if (null != node.left) {
            minMaxL = dfs1026(node.left);
            max1026 = Math.max(max1026, Math.abs(node.val - minMaxL[0]));
            max1026 = Math.max(max1026, Math.abs(node.val - minMaxL[1]));
        }
        int[] minMaxR = new int[]{node.val, node.val};
        if (null != node.right) {
            minMaxR = dfs1026(node.right);
            max1026 = Math.max(max1026, Math.abs(node.val - minMaxR[0]));
            max1026 = Math.max(max1026, Math.abs(node.val - minMaxR[1]));
        }
        int[] minMax = new int[2];
        minMax[0] = Math.min(node.val, Math.min(minMaxL[0], minMaxR[0]));
        minMax[1] = Math.max(node.val, Math.max(minMaxL[1], minMaxR[1]));
        return minMax;
    }

    //p1140
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] preSum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + piles[i];
        }
        return dfs1140(new HashMap<>(), preSum, n, 0, 1);
    }
    private int dfs1140(Map<Integer, Integer> cache, int[] preSum, int n, int i, int m) {
        if (2 * m >= n - i) {
            return preSum[n] - preSum[i];
        }
        int key = i * 1000 + m;
        Integer maxStone = cache.get(key);
        if (null != maxStone) {
            return maxStone;
        }
        maxStone = 0;
        for (int x = 1; x <= 2 * m; ++x) {
            maxStone = Math.max(maxStone, preSum[n] - preSum[i] - dfs1140(cache, preSum, n, i + x, Math.max(m, x)));
        }
        cache.put(key, maxStone);
        return maxStone;
    }

    //1105
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        return dfs1105(shelfWidth, books, new int[n], new boolean[n], n - 1);
    }
    private int dfs1105(int shelfWidth, int[][] books, int[] cache, boolean[] visited, int i) {
        if (i < 0) return 0;
        if (i == 0) {
            cache[0] = books[0][1];
            visited[0] = true;
            return books[0][1];
        }
        if (visited[i]) {
            return cache[i];
        }
        int widthSum = books[i][0];
        int minHeight = dfs1105(shelfWidth, books, cache, visited, i - 1) + books[i][1];
        int tierHeight = books[i][1];
        for (int j = i - 1; j >= 0; --j) {
            widthSum += books[j][0];
            tierHeight = Math.max(tierHeight, books[j][1]);
            if (shelfWidth >= widthSum) {
                minHeight = Math.min(minHeight, dfs1105(shelfWidth, books, cache, visited, j - 1) + tierHeight);
            } else {
                break;
            }
        }
        cache[i] = minHeight;
        visited[i] = true;
        return minHeight;
    }

    //p1145
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        //找到x的父节点
        TreeNode parent = findParentForTarget1145(root, x);
        TreeNode node;
        if (null == parent) {
            //x是根节点
            node = root;
        } else {
            //x是parent的左子节点或右子节点
            if (null != parent.left && parent.left.val == x) {
                node = parent.left;
            } else {
                node = parent.right;
            }
        }
        //x左子结点的子节点数量
        int b = dfsCountNode1145(node.left);
        //x右子结点的子节点数量
        int c = dfsCountNode1145(node.right);
        //除x这颗子树之外的所有节点数量
        int a = node == root ? 0 : (n - (b + c + 1));
        //考虑x周围有3个邻接点
        //从贪心的角度，作为蓝方玩家，要么抢占x的左子节点，要么抢占x的右子节点，要么抢占x的父节点
        //这样就能占领x的其中一条邻边以及相连的所有节点，并且蓝方抢占之后可以堵住红方继续渗透
        //因此有a、b、c这3个值，蓝方可以占领的最大节点数是其中之一，而红方是其余两个值
        //只要其中一个值大于其余两个值+1（因为还要考虑红方先手），蓝方就可以必胜
        return a > (b + c + 1) || b > (a + c + 1) || c > (a + b + 1);
    }
    private int dfsCountNode1145(TreeNode node) {
        if (null == node) {
            return 0;
        }
        return 1 + dfsCountNode1145(node.left) + dfsCountNode1145(node.right);
    }
    private TreeNode findParentForTarget1145(TreeNode cur, int target) {
        if (null == cur || cur.val == target) {
            return null;
        }
        if ((null != cur.left && cur.left.val == target) || (null != cur.right && cur.right.val == target)) {
            return cur;
        }
        TreeNode result = findParentForTarget1145(cur.left, target);
        if (null == result) {
            result = findParentForTarget1145(cur.right, target);
        }
        return result;
    }

    /**
     * 1349【位运算+动态规划】参加考试的最大学生数
     */
    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length, N = 1 << n;
        //预处理，找出每一行每一种有效的入座可能状态，采用位运算的方式记录入座状态
        boolean[][] compliantMat = new boolean[m][N];
        for (int i = 0; i < m; ++i) {
            for (int state = 0; state < N; ++state) {
                compliantMat[i][state] = true;
                int prevBit = 0, bit;
                for (int j = 0; j < n; ++j) {
                    bit = (state & (1 << (n - 1 - j))) > 0 ? 1 : 0;
                    if (bit == 1) {
                        if (seats[i][j] == '#' || prevBit == bit) {
                            //同一行内，如果坐了坏的位置或没有间隔开，都不能算有效状态
                            compliantMat[i][state] = false;
                            break;
                        }
                    }
                    prevBit = bit;
                }
            }
        }
        //保存每一行所有入座可能性下，基于后面一行的情况可以入座的最大人数
        int[][] dp = new int[m][N];
        //先计算最后一行学生的每一种有效落座情况下的入座人数
        int i = m - 1;
        for (int state = 0; state < N; ++state) {
            if (compliantMat[i][state]) {
                dp[i][state] = Integer.bitCount(state);
            } else {
                dp[i][state] = Integer.MIN_VALUE;
            }
        }
        --i;
        for (; i >= 0; --i) {
            for (int state = 0; state < N; ++state) {
                if (!compliantMat[i][state]) {
                    dp[i][state] = Integer.MIN_VALUE;
                } else {
                    //如果当前行的state状态是有效的，计算state状态的入座人数
                    int cnt = Integer.bitCount(state), prevI = i + 1;
                    for (int prevState = 0; prevState < N; ++prevState) {
                        //采用遍历上一行的状态的方式寻找在prevState情形下state也是有效的情况
                        if (compliantMat[prevI][prevState] && ((state & (prevState << 1)) == 0) && ((state & (prevState >> 1)) == 0)) {
                            //prevState左移或右移一个位置都不会与state的位置产生重叠，说明在prevState有效的情况下，state不会产生作弊
                            dp[i][state] = Math.max(dp[i][state], dp[prevI][prevState] + cnt);
                        }
                    }
                    //当前行的state结果至少也是state状态的入座人数
                    dp[i][state] = Math.max(dp[i][state], cnt);
                }
            }
        }
        int answer = Integer.MIN_VALUE;
        for (int state = 0; state < N; ++state) {
            //计算第一行所有入座情况下最多可以入座的人数
            answer = Math.max(answer, dp[0][state]);
        }
        return answer;
    }

    /**
     * 1462【DFS】课程表 IV
     */
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        //graph initialization
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            graph[i] = new ArrayList<>();
        }
        boolean[][] requisites = new boolean[numCourses][numCourses];
        for (int[] prerequisite : prerequisites) {
            int a = prerequisite[0], b = prerequisite[1];
            graph[a].add(b);
        }
        boolean[] visited = new boolean[numCourses];
        for (int i = 0; i < numCourses; ++i) {
            dfs1642(requisites, graph, visited, numCourses, i);
        }
        List<Boolean> answer = new ArrayList<>(queries.length);
        for (int[] query : queries) {
            answer.add(requisites[query[0]][query[1]]);
        }
        return answer;
    }
    private void dfs1642(boolean[][] requisites, List<Integer>[] graph, boolean[] visited, int numCourses, int a) {
        if (visited[a]) return;
        visited[a] = true;
        for (int next : graph[a]) {
            dfs1642(requisites, graph, visited, numCourses, next);
            requisites[a][next] = true;
            for (int i = 0; i < numCourses; ++i) {
                requisites[a][i] = requisites[a][i] | requisites[next][i];
            }
        }
    }

    /**
     * 2003【DFS+启发式合并】每棵子树内缺失的最小基因值
     */
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        //初始化结果，最小的缺失基因值肯定最小为1
        int[] answer = new int[n];
        Arrays.fill(answer, 1);
        //邻接矩阵初始化
        List<Integer>[] children = new List[n];
        for (int i = 1; i < n; ++i) {
            List<Integer> neList = children[parents[i]];
            if (null == neList) neList = new ArrayList<>();
            neList.add(i);
            children[parents[i]] = neList;
        }
        //记录每个节点作为子树的情况下整颗子树的所有节点基因集合
        Set<Integer>[] geneSets = new Set[n];
        for (int i = 0; i < n; ++i) {
            geneSets[i] = new HashSet<>();
        }
        dfs2003(nums, answer, children, geneSets, 0);
        return answer;
    }
    private int dfs2003(int[] nums, int[] answer, List<Integer>[] children, Set<Integer>[] geneSets, int cur) {
        //当前节点加入到当前节点作为子树的基因集合中
        geneSets[cur].add(nums[cur]);
        if (null != children[cur]) {
            for (int child : children[cur]) {
                //逐个子节点进行DFS，返回的结果是该子节点作为子树时缺少的最小基因值，当前节点cur的答案一定大于等于各子节点答案的最大值
                answer[cur] = Math.max(answer[cur], dfs2003(nums, answer, children, geneSets, child));
                //启发式合并，每次都将小的集合合并到大的集合，如果geneSets[cur].size() < geneSets[child].size()，则交换集合再合并
                if (geneSets[cur].size() < geneSets[child].size()) {
                    Set<Integer> t = geneSets[cur];
                    geneSets[cur] = geneSets[child];
                    geneSets[child] = t;
                }
                geneSets[cur].addAll(geneSets[child]);
            }
        }
        while (geneSets[cur].contains(answer[cur])) {
            //如果当前节点的结果在子树中存在，则枚举一个稍大的值作为缺失的最小基因值结果
            answer[cur]++;
        }
        //返回的结果是当前节点作为子树时缺少的最小基因值
        return answer[cur];
    }

    //p2049
    public int countHighestScoreNodes(int[] parents) {
        if (parents.length < 2) {
            return 0;
        }
        MultiChildrenNode[] nodes = new MultiChildrenNode[parents.length];
        nodes[0] = new MultiChildrenNode(0);
        //重建多叉树，O(n)
        for (int i = 1; i < parents.length; ++i) {
            if (null == nodes[i]) {
                nodes[i] = new MultiChildrenNode(i);
            }
            if (null == nodes[parents[i]]) {
                nodes[parents[i]] = new MultiChildrenNode(parents[i]);
            }
            nodes[parents[i]].children.add(nodes[i]);
        }
        //整理所有节点的子孙数目，O(n)
        dfsCountSubNode(nodes[0]);
        int highestScoreCount = 1;
        long highestScore = 1L;
        for (MultiChildrenNode child : nodes[0].children) {
            highestScore *= (child.subNodeCount + 1);
        }
        //计算每个节点的score，O(n)，注意乘积很大，需要用long
        for (int i = 1; i < parents.length; ++i) {
            long score = (nodes[0].subNodeCount + 1) - nodes[i].subNodeCount - 1;
            for (MultiChildrenNode child : nodes[i].children) {
                score *= (child.subNodeCount + 1);
            }
            if (score == highestScore) {
                ++highestScoreCount;
            } else if (score > highestScore) {
                highestScore = score;
                highestScoreCount = 1;
            }
        }
        return highestScoreCount;
    }

    /**
     * 采用DFS方式遍历多叉树统计所有子孙节点的数目
     */
    private void dfsCountSubNode(MultiChildrenNode node) {
        //node节点的所有子孙节点数目 = sum(子节点的数目 + 每个子节点的子孙数目)
        int subNodeCount = 0;
        for (MultiChildrenNode child : node.children) {
            //先深度整理子节点的子孙数目
            dfsCountSubNode(child);
            //子节点
            ++subNodeCount;
            //子节点的子孙节点数目
            subNodeCount += child.subNodeCount;
        }
        node.subNodeCount = subNodeCount;
    }

    /**
     * 记录树节点的所有子孙节点数目
     */
    static class MultiChildrenNode {
        int val;
        int subNodeCount;
        List<MultiChildrenNode> children;

        public MultiChildrenNode(int val) {
            this.val = val;
            subNodeCount = 0;
            children = new ArrayList<>();
        }

        @Override
        public String toString() {
            return val + "";
        }
    }

    /**
     * 2304【动态规划】网格中的最小路径代价
     */
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        int[] rowState = new int[n];
        System.arraycopy(grid[0], 0, rowState, 0, n);
        for (int i = 0; i < m - 1; ++i) {
            int[] nextRowState = new int[n];
            Arrays.fill(nextRowState, Integer.MAX_VALUE);
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    nextRowState[j] = Math.min(nextRowState[j], rowState[k] + moveCost[grid[i][k]][j] + grid[i + 1][j]);
                }
            }
            rowState = nextRowState;
        }
        int answer = Integer.MAX_VALUE;
        for (int j = 0; j < n; ++j) {
            answer = Math.min(answer, rowState[j]);
        }
        return answer;
    }

    /**
     * 2316【DFS】统计无向图中无法互相到达点对数
     */
    public long countPairs(int n, int[][] edges) {
        Set<Integer>[] graph = new HashSet[n];
        for (int[] edge : edges) {
            Set<Integer> nei = graph[edge[0]] != null ? graph[edge[0]] : new HashSet<>();
            nei.add(edge[1]);
            graph[edge[0]] = nei;
            nei = graph[edge[1]] != null ? graph[edge[1]] : new HashSet<>();
            nei.add(edge[0]);
            graph[edge[1]] = nei;
        }
        boolean[] visited = new boolean[n];
        long answer = 0;
        int sumOfVisited = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                int gs = dfs2316(graph, visited, i);
                answer += (long) gs * (n - gs - sumOfVisited);
                sumOfVisited += gs;
            }
        }
        return answer;
    }
    private int dfs2316(Set<Integer>[] graph, boolean[] visited, int node) {
        int count = 1;
        visited[node] = true;
        Set<Integer> nei = graph[node];
        if (null == nei) return count;
        for (int ne : nei) {
            if (!visited[ne]) {
                count += dfs2316(graph, visited, ne);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        DfsSolution solution = new DfsSolution();
        Assert.isTrue(46 == solution.knightDialer(3));
        Assert.isTrue(10 == solution.knightDialer(1));
        Assert.isTrue(20 == solution.knightDialer(2));
        Assert.isTrue(136006598 == solution.knightDialer(3131));
//        Assert.isTrue(4 == solution.maxStudents(Parser.parseBoard("[[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],[\".\",\"#\",\"#\",\"#\",\"#\",\".\"],[\"#\",\".\",\"#\",\"#\",\".\",\"#\"]]")));
//        Assert.isTrue(3 == solution.maxStudents(Parser.parseBoard("[[\".\",\"#\"],[\"#\",\"#\"],[\"#\",\".\"],[\"#\",\"#\"],[\".\",\"#\"]]")));
    }
}
